import java.util.*;


class StockSpanner {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public StockSpanner() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }

    public int next(int price) {
        int ret=1;
        while (!stack1.isEmpty()&&stack1.peek()<=price){
            stack1.pop();
            ret+=stack2.pop();
        }
        stack1.push(price);
        stack2.push(ret);
        return ret;
    }
}








public class project {
    public boolean parseBoolExpr(String expression) {
        Deque<Character> deque1=new ArrayDeque<>();
        Deque<Character> deque2=new ArrayDeque<>();
        for(int i=0;i<expression.length();i++){
            char ch=expression.charAt(i);
            if(ch=='('||ch=='f'||ch=='t'){
                deque1.push(ch);
            }else if(ch=='!'||ch=='&'||ch=='|'){
                deque2.push(ch);
            }else if(ch==')'){
                char symbol=deque2.pop();
                boolean flag= symbol=='&';
                while (!deque1.isEmpty()){
                    char sign=deque1.pop();
                    if(sign=='('){
                        break;
                    }else if(symbol=='&'){
                        flag &=(sign=='t');
                    }else if(symbol=='|'){
                        flag |=(sign=='t');
                    }else{
                        flag = sign=='f';
                    }
                }
                deque1.push(flag?'t':'f');
            }
        }
        return deque1.pop()=='t';
    }





















    public String decodeString(String s) {
        StringBuilder sb=new StringBuilder();
        int index=0;
        int len=s.length();
        LinkedList<Integer> listCount=new LinkedList<>();
        LinkedList<String> listStr=new LinkedList<>();
        int count=0;
        while (index<len){
            char ch=s.charAt(index);
            if(ch=='['){
                listCount.addLast(count);
                listStr.addLast(sb.toString());
                sb=new StringBuilder();
                count=0;
            }else if(ch==']'){
                StringBuilder tmp=new StringBuilder();
                int curCount=listCount.removeLast();
                for(int i=0;i<curCount;i++){
                    tmp.append(sb);
                }
                sb=new StringBuilder(listStr.removeLast()+tmp);
            }else if(ch>='0'&&ch<='9'){
                count=count*10+Integer.parseInt(ch+"");
            }else{
                sb.append(ch);
            }
            index++;
        }
        return sb.toString();
    }



















    public int[] exclusiveTime(int n, List<String> logs) {
        Stack<Integer> stack=new Stack<>();
        String[] s=logs.get(0).split(":");
        stack.add(Integer.parseInt(s[0]));
        int prev=Integer.parseInt(s[2]);
        int index=1;
        int[] ret=new int[n];
        while (index<logs.size()){
            String[] str=logs.get(index).split(":");
            if(str[1].equals("start")){
                if(!stack.isEmpty()){
                    ret[stack.peek()]+=Integer.parseInt(str[2])-prev;
                }
                stack.add(Integer.parseInt(str[0]));
                prev=Integer.parseInt(str[2]);
            }else{
                ret[stack.pop()]+=Integer.parseInt(str[2])-prev+1;
                prev=Integer.parseInt(str[2])+1;
            }
            index++;
        }
        return ret;
    }






















    public int lengthLongestPath(String input) {
        int len=input.length();
        int index=0;
        int ret=0;
        Stack<Integer> stack=new Stack<>();
        while (index<len){
            int layer=1;
            while (index<len&&input.charAt(index)=='\t'){
                index++;
                layer++;
            }
            boolean flag=false;
            int size=0;
            while (index<len&&input.charAt(index)!='\n'){
                if(input.charAt(index)=='.'){
                    flag=true;
                }
                size++;
                index++;
            }
            index++;
            while (stack.size()>=layer){
                stack.pop();
            }
            if(!stack.isEmpty()){
                size+=stack.peek()+1;
            }
            if(flag){
                ret=Math.max(size,ret);
            }else{
                stack.push(size);
            }
        }
        return ret;
    }
}
